package com.yty.demo._2_recursion;

/**
 * @author: yangtaoyao
 * @time: 2020/1/6$ 12:37$
 * @description: 递归调用
 */
public class RecursionTest {
    public static void main(String[] args) {
        System.out.println(method1(5));
        System.out.println(method2(5));
        System.out.println("========================");
        System.out.println(fibonacci(15));
        System.out.println(fibonacci2(15));

    }

    /**
     * @param
     * @description: 递归求阶乘
     * @return:
     * @author: yangtaoyao
     * @time: 2020/1/6 12:39
     */
    private static int method1(int i) {
        if (i == 1) {
            return 1;
        } else {
            return i * method1(i - 1);
        }
    }

    /**
     * @description: 线性求阶乘
     */
    private static int method2(int i) {
        int res = 1;
        for (int j = i; j > 0; j--) {
            res *= j;
        }
        return res;
    }

    /**
     * Fibonacci数列：F1=F2=1;Fn=F(n-1)+F(n-2);n>2;
     */
    private static int fibonacci(int n) {
        if (n == 1 || n == 2) {
            return 1;
        } else {
            return fibonacci(n - 1) + fibonacci(n - 2);
        }
    }

    /**
     * 非递归
     * 1 2 3 4 5
     * 1 1 2 3 5
     */
    private static int fibonacci2(int n) {
        if (n == 1 || n == 2)
            return 1;
        int f1 = 1, f2 = 1;
        int fn = 0;
        for (int i = 3; i <= n; i++) {
            fn = f1 + f2;
            f1 = f2;
            f2 = fn;
        }
        return fn;
    }
}
